zk-SNARKs | setup-prooving-verifying
zk-SNARKsとは、ある計算が正しく行われたことをその計算の課程を省略して第三者に証明することができること。この「計算」は任意の計算であるので多くの適用可能な事例があげられる。
multi tokens batch auction on plasma
auctionが数理モデルに基づいて行われたかZKP
Coda protocol
ブロックチェーンがスケールするほど検証するのが大変になる
スマートコントラクトが実行される前にユーザーに対して正当性を証明する。
truebitはvertification gameによるoff-chain computationなのに対し、zk-SNARKsはZKPによるoff-chain computation。
zk-snarks on ethereum
Byzantiumでbn256Add, bn256ScalarMul, bn256Pairingの追加
https://gyazo.com/b48904355602c70a145f355cb004bc1a
https://gyazo.com/2d5a21fcdad1923822cc48f01799c97b
trusted setup
楕円曲線上の点P, Q, R, Sにおいて $ P * k = Qの時、R,SがそれぞれP, Qから計算できない場合は$ R * kは計算することができない。逆に、R = rP, S = rQとなるようなrを知っている場合はS＝kRを得ることができる。
例えば、証明者アリスが(R, S) = (rP, rQ)となるrを知っているとすると、
S = rQ = r(kP) = k(rP) = kR
と確かに得ることができる。
楕円曲線上の点P, Q, R, Sを考える。$ P * k = QであるP, Qに対して$ kの値は誰も知らない。（セットアップ後を想定）このような時、$ R * k = Sである、(R ,S)を作るにはKEAより、P, Qに対して秘匿な値r を乗算して作るしかない。
ただし、ペアリングの性質により$ R * k = Sを検証するために$ kを知る必要はなく$ e(R, Q) = e(P, S)を検証すればいい。
楕円曲線上で$ P_i * k = Q_iが成立する10個の点$ (P_1, Q_1), (P_2, Q_2) ... (P_{10}, Q_{10})を考える。
kを知らない状況で、$ R * k = Sとなる楕円曲線上の点(R, S)を作るためには、係数$ i_1, i_2 ... i_{10}を利用して、$ P_1 * i_1 + P_2 * i_2 + ... + P_{10} * i_{10}という線形和からRを知る必要がある。（Qについても同様）
$ R * k = Sとなることは、ペアリングによる検証が可能。
例えば、(P1, Q1)(P2, Q2)で考えると、 i1, i2を$ F_q^*の元として
$ S = i_1Q_1 + i_2Q_2 = i_1kP1 + i_2kP_2 = k(i_1P_1 + i_2P_2) = kR
一般的に、
$ (a', b') = (\Sigma^d_{i=1}c_ia_i, \Sigma^d_{i=1}c_ib_i)
つまり、線形和の検証を行いたい10個のPに対して、$ kを知らずに対応するQを作ることができない。そして、もし$ kを知っていれば線形和を作ることなく任意のRに対して、$ R * k = Sとなる(R, S)のペアを作ることができる。
このことが、zk-SNARKsでtrustedなセットアップが必要となる理由。つまり、信頼できる主体が10個の点(P, Q)を作ったら$ kを消去する必要がある。$ kが存在するとKEAが成り立たない。
vkをハードコードしたコントラクトをsetuperがデプロイ。
QAPからproofsの生成
public inputと計算したwitness(from private input)からproverはsecretベクトルを計算できる。このsecretベクトルを用いてproofを生成する。
$ A(x) * B(x) - C(x) = H(x) * Z(x)なる多項式セット(A, B, C, Z)がQAPにより与えられる。実際のユースケースでは、250kなどののcircuit gates (constraints)となるので、QAPを用いて全てのconstraintsを一気に証明・検証していく。 $ tを多項式を評価するsecret point、Gはgenerator pointとして以下の値をtrusted setupに加える。
・$ G * A_1(t), G * A_1(t) * k_a
・$ G * A_2(t), G * A_2(t) * k_a
・…
・$ G * B_1(t), G * B_1(t) * k_b
・$ G * B_2(t), G * B_2(t) * k_b
・…
・$ G * C_1(t), G * C_1(t) * k_c
・$ G * C_2(t), G * C_2(t) * k_c
・…
このうち、$ t, k_a, k_b, k_cはtoxic wasteでセットアップが完了したら捨てなければならない。もしこれらの値を持っていたら不正な証明（本当は証明できていないのに証明できているような証明）を作ることができてしまう。
$ P * k_a = QとなるP, Qが与えられたら（$ k_aは知らずにペアリングで検証可能）、tで評価された$ A_iの多項式の線形和が分かる。
よって証明者は、$ t, k_a, k_b, k_cを知ることなく、trusted setupで追加された点から以下の値を計算し、proofsとして提供することができる。
つまり、trusted setupで(P, Q)が与えられ、KEAより（R, S)が生成できることがゼロ知識証明になっている。要は、Pの線形和を生成することが可能かということにゼロ知識を帰着させている。
$ kを知っていると(R, S)が作れてしまう。
proofs
π_a = G * A(t), π’_a = G * A(t) * k_a
π_b = G * B(t), π’_b = G * B(t) * k_b
π_c = G * C(t), π’_c = G * C(t) * k_c
例えば、$ A(t)は$ A_i(t)の線形和であり、KEAに基づいている。つまり、$ A(t)は$ Rに相当し、$ A_i(t)が$ P_iに相当してる。
なので、証明者が命題の解を知っている場合に限り、それぞれの多項式の正当な線形和を算出することができる。「正当な」とは、後述の検証をパスすること。
setuperは線形和における係数を知る必要なくsetupできるので命題の解を知ることなくsetupできる。
proverのみが知っているsolutionベクトルを$ s = (s_1, s_2, s_3)とすると、
$ A(t) = s_1A_1(t) + s_2A_2(t) + s_3A_3(t)
Proving Key : 正当なA, B, Cを持っているか
・$ G * A_1(t), G * A_1(t) * k_a
・$ G * A_2(t), G * A_2(t) * k_a
・…
・$ G * B_1(t), G * B_1(t) * k_b
・$ G * B_2(t), G * B_2(t) * k_b
・…
・$ G * C_1(t), G * C_1(t) * k_c
・$ G * C_2(t), G * C_2(t) * k_c
・…
toxic waste
・$ t, k_a, k_b, k_c
同じ係数が使われていることの証明
3つの線形和全てが同じ係数であることを証明するために、$ G * (A_i(t) + B_i(t) + C_i(t)) * bをtrusted setupに追加する。（bもtoxic waste）
これにより、証明者はペアリングを使ってA+B+Cがセットアップの値と同じか検証することで、同じ係数の線形和を作ることが可能になる。（上記より、A, B, Cそれぞれの線形和の証明は行うことができたが、A, B, Cそれぞれ互いの線形和の係数が一致しているかは証明できていない）
QAPがZで割り切れることの証明
また、e(π_a, π_b) / e(π_c, G) ?= e(π_h, G * Z(t))が成り立つか検証できるようにするために、$ A * B - C = H * Zであることも証明する必要がある。 π_h = G * H(t)
$ Hを楕円曲線上の点にすることは難しい。$ Hはただの多項式であり、それぞれのQAPにおける係数をあらかじめ知っておくための時間はほとんどないので、trusted setupに以下のデータを加えておく必要がある。
$ G, G * t, G * t^2, G * t^3, G * t^4 ...
これにより、$ Hのそれぞれの項を楕円曲線上の点として扱うことができそれを加算しているので$ Hも楕円曲線上の点となる。
証明者が検証者に対して全てのデータを提供できるように、あるQAPにおいてH(t)がいつでも確実に計算できるようにしておく必要がある。Zcashのセットアップでは実現するために、上記のシーケンスが100万まで続く。
証明(pk)は8つの楕円曲線上の点を含む。(π_kだけ$ G_2の要素）
π_a = G * A(t)
π’_a = G * A(t) * k_a
π_b = G * B(t)
π’_b = G * B(t) * k_b
π_c = G * C(t)
π’_c = G * C(t) * k_c
π_d ( $ =G * (A(t) + B(t) + C(t)) * k_d )
π_h( $ = G * H(t))
これらのうち、π_b以外は$ F_pカーブ上の点であり、それぞれ32bytes。π_bは$ F_{b^2}カーブ上にあり、64bytes。なので、証明サイズは合計288bytes。
証明の生成が計算量的に大変な2つの部分
Hを得るためにA * B - CをZで除算する部分。（高速フーリエ変換で緩和可能だがそれでも厳しい）
A(t), B(t), C(t), H(t)とそれぞれに対応するペアを作るための乗算、加算の演算
Proverのassignmentに対する追加保護
正しいassiginmentが$ s_1 ... s_mだとして（例えばつまり、$ A = s_1A_1 + ... +s_mA_m）対応するA,B,C,Hが存在するとする。ここで他の人が$ s'_1,...,s'_mをassignmentとして用いて対応するA',B',C',H'を計算することができた時、$ s'_1,...,s'_mはProverのassignmentではないことを推定できてしまう。
そこで、Proverは自身のassignmentを秘匿化するためにランダム値をそれぞれの多項式に加える。
Az = A + δ1*Z
Bz = B + δ2*Z
Cz = C + δ3*Z
ここで、A*B-C=H*Zを想定しているので、それぞれのランダム値にZを掛け合わせることでHを再定義し、$ A_z*B_z-C_z = H_z * Tで表すことができる。
Vertification Key
$ vk_a = G * k_a :2
$ vk_b = G * k_b :2
$ vk_c = G * k_c :2
$ vk_z = G * Z(t) :4
$ vk_e = G * k_e :3
$ vk_{de} = G * k_d * k_e : 3
検証者によるproofの検証
５個のペアリング検証。
Verification Key
G * Z(t) : 4
G, G * t, G * t², G * t³, G * t⁴ …. : 4
G * (A_i(t) + B_i(t) + C_i(t)) * b : 3
toxic waste
b
1. 特定のパラメーターに対する"cutstom vertification key"の生成を行う関数の処理
ほとんどの場合、ゼロ知識証明を行いたいケースでは関数の挙動を抽象的にゼロ知識証明するのではなく、特定の関数に地して指定したパラメーターを与えた時のoutputに対してゼロ知識証明したい。
$ decrypt(balance_{old}, k) - decrypt(txValue, k) = decrypt(balance_{new}, k)
例えば、balance_old, txValue, balance_newの3つの変数は公開されており、これらのinputに制限した検証鍵を生成する必要がある。
zokratesではdef main()に入れるpublic inputおよび定義したoutputに相当。
2. A, B, Cそれぞれに対して線形和が一致しているか検証
以下のproofを検証。
π_a = G * A(t)
π’_a = G * A(t) * k_a
π_b = G * B(t)
π’_b = G * B(t) * k_b
π_c = G * C(t)
π’_c = G * C(t) * k_c
以下のペアリングが成立すればOK。
e(π_a, G * k_a) = e(π'_a, G)
e(π_b, G * k_b) = e(π'_b, G)
e(π_c, G * k_c) = e(π'_c, G)
例えば、証明鍵により、$ (P_i, Q_i) = (A_i(t)G, k_a *A_i(t)G)として$ Q_i = k_a * P_iが与えられている。
$ \pi_a' = k_a * \pi_aとなるようなproofを与えるためには、KEAにより
$ \pi_a = a_1 * A_1(t)G + a_2 * A_2(t)G + ....
となるような係数$ a_iを知っている必要がある。（$ \pi_a'についても同様）
この$ a_iがQAPにwitnessをinputすることにより得られる多項式係数ベクトルであり、$ \pi_aを$ P_iの線形和で表せていることになる。
つまり、$ a_iを知らないと証明$ \pi_aを証明鍵$ A_i(t)Gで表すことができず、上記のペアリングが成立し得ない。
3. 線形和が同じ係数を持っているか検証
以下のproofを検証。
π_d( $ =G * (A(t) + B(t) + C(t)) * k_d )
以下のペアリングが成立。
e(π_d, vk_e) = e(π_a + π_b + π_c, vk_de)
$ (A_i + B_i + C_i)Gに対するasignmentの線形和が$ \pi_a, \pi_b, \pi_cからの$ (A+B+C)Gと一致すれば、確かにそれぞれのA,B,Cに対して同じassignmentがかけられていることが分かる。
4. A * B - C = H * Zの検証
以下のproofを検証。
π_h( $ = G * H(t))
以下のペアリングが成立すればOK。
$ e(\pi_a, \pi_b) = e(\pi_h, Z(t)G)e(\pi_c, G)
zk-SNARKs早見表(orizinalでは$ G_1only)
https://gyazo.com/83129a24421586ec258da66b69a6a390
資料まとめ
se-snark
coda protocolのベースになっているrecursive composition of zk-SNARKs
DLPをベースにFiat-Shamir heuristicを使って（Hyraxと名付けてる）proofのサイズを小さくし、proverとverifierの計算コストも3/5くらいに。
libsnarks開発チームによるcircuits計算を分散化して従来のzk-snarksより100倍早く計算できるようにするプロトコル
アップデート可能なCRS。CRSサイズは大きくなってしまう。
layer1とlayer2はバランス良く開発されていく必要があるが、長期的に見るとlayer2がでっかくなっていくというお話。
QAPの原論文。全てのconstraintsを多項式でひとつにまとめる。
SNARKsの名付け論文
いわゆるGroth16
Pinocchioの評価
snark, stark比較
MINT curveでのecrecover in snarks
ライブラリ